package leetcode.dynamic_programming;

/**
 * @author mgl
 * @version 1.0
 * @description 最小路径和 leetcode64题
 * @date 2023/10/4 17:42
 */
public class MinPathSum {

    public int minPathSum(int[][] grid) {

        int row = grid.length;
        int column = grid[0].length;
        int[][] arr = new int[row][column];
        arr[0][0] = grid[0][0];

        for (int i = 0; i < column; i++) {
            for (int j = 0; j < row; j++) {
                if (j - 1 >= 0 && i - 1 >= 0) {
                    arr[j][i] = grid[j][i] + Math.min(arr[j - 1][i], arr[j][i - 1]); //如果左边和上面都不为空，取这两个的最小值与当前节点权重相加
                } else if (j - 1 >= 0) {
                    arr[j][i] = grid[j][i] + arr[j - 1][i]; //上面不为空，取上面的权重加上当前节点的权重
                } else if (i - 1 >= 0) {
                    arr[j][i] = grid[j][i] + arr[j][i - 1]; //左面不为空，取左面的权重加上当前节点的权重
                }
            }

        }

        return arr[row - 1][column - 1];
    }

    public static void main(String[] args) {
        int[][] arr = new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(new MinPathSum().minPathSum(arr));
    }
}
